﻿using System;
using System.Collections.Generic;
using System.Linq;
using Algoritmia.DataStructures.Maps;
using Algoritmia.Schemes;
using Algoritmia.StateSpaces;
using Algoritmia.Utils;
using Sets = Algoritmia.DataStructures.Sets;
using Lists = Algoritmia.DataStructures.Lists;

namespace Algoritmia.Problems.PerfectHash.Improved
{
    public class PerfectHashStateSpace2 : Basic.PerfectHashStateSpace,
        IReversibleForwardStateSpace<PerfectHashStateSpace2.State, int>
    {
        #region Inner Classes
        public new class State 
        {
            public Sets.ISet<int> UsedValues { get; private set; }
            private readonly Func<IMap<char, int>> _createMap;

            public IMap<char, Lists.IList<string>> Available { get; private set; }
            public readonly List<char> Chars;
            public IMap<char, int> G { get; private set; }
            public int Index;

            public State(IEnumerable<string> words, Func<IMap<char, int>> createMap = null)
            {
                _createMap = createMap ?? (() => AlgoritmiaFactory.Maps<char, int>.Default);
                Chars = (from w in words
                         select w[0]).Union(from w in words
                                            select w.Last()).ToList();
                G = _createMap();
                Index = 0;

                var freq = _createMap();
                foreach(var w in words)
                {
                    freq[w[0]] = freq.Get(w[0], 0) + 1;
                    freq[w.Last()] = freq.Get(w.Last(), 0) + 1;
                }
                Chars.Sort((a,b) => -(freq[a].CompareTo(b)));
                Available = AlgoritmiaFactory.Maps<char, Lists.IList<string>>.Default;
                foreach(var c in Chars)
                {
                    Available[c] = AlgoritmiaFactory.Lists<string>.Default;
                }
                var seenWords = AlgoritmiaFactory.Sets<string>.Default;
                var seenChars = AlgoritmiaFactory.Sets<char>.Default;
                foreach(var c in Chars)
                {
                    seenChars.Add(c);
                    foreach(var w in words)
                    {
                        if ( !seenWords.Contains(w) && seenChars.Contains(w[0]) && seenChars.Contains(w.Last()))
                        {
                            seenWords.Add(w);
                            Available[c].Add(w);
                        }
                    }
                }
                UsedValues = AlgoritmiaFactory.Sets<int>.Default;

            }
        }

        #endregion

        public PerfectHashStateSpace2(IEnumerable<string> words, int maxValue, Func<int, Sets.ISet<int>> createSet = null)
            : base(words,maxValue,createSet)
        {
        }

        #region Implementation of IForwardStateSpace<State,int>

        public State Decide(State state, int decision)
        {
            state.G[state.Chars[state.Index]] = decision;
            foreach(var w in state.Available[state.Chars[state.Index]])
            {
                state.UsedValues.Add(w.Length + state.G[w[0]] + state.G[w.Last()]);
            }
            state.Index++;
            return state;
        }

        public IEnumerable<int> Decisions(State state)
        {
            for (int i = 0; i < _maxValue; i++)
            {
                if (ValueIsPromising(state, i))
                    yield return i;
            }
        }

        public new IEnumerable<State> InitialStates
        {
            get { yield return new State(_words); }
        }

        public bool IsFinal(State state)
        {
            return state.Index == state.Chars.Count;
        }

        #endregion

        #region Implementation of IReversibleForwardStateSpace<State,int>

        public State Undo(State state, int decision)
        {
            state.Index--;
            foreach(var w in state.Available[state.Chars[state.Index]])
            {
                state.UsedValues.Remove(w.Length + state.G[w[0]] + state.G[w.Last()]);
            }
            state.G.Remove(state.Chars[state.Index]);
            return state;
        }

        #endregion

        private static bool ValueIsPromising(State s, int n)
        {
            var alsoUsed = AlgoritmiaFactory.Sets<int>.Default;
            foreach(var w in s.Available[s.Chars[s.Index]])
            {
                int? a = null, b = null;
                if (w[0] == s.Chars[s.Index]) a = n;
                else if (s.G.Contains(w[0])) a = s.G[w[0]];
                if (w.Last() == s.Chars[s.Index]) b = n;
                else if (s.G.Contains(w.Last())) b = s.G[w.Last()];

                if ( a != null && b != null)
                {
                    var h = w.Length + a.Value + b.Value;
                    if (s.UsedValues.Contains(h) || alsoUsed.Contains(h))
                    {
                        return false;
                    }
                    alsoUsed.Add(h);
                }

            }
            return true;
        }

        public IEnumerable<KeyValuePair<string, int>> Solution(State finalState)
        {
            foreach (var word in _words)
            {
                var h = word.Length + finalState.G[word[0]] + finalState.G[word.Last()];
                yield return new KeyValuePair<string, int>(word, h);
            }
        }
    }

    public class PerfectHashFinder
    {
        private readonly BacktrackingEnumerator<PerfectHashStateSpace2.State, int, IEnumerable<KeyValuePair<string, int>>> _enumerator;

        public PerfectHashFinder()
        {
            _enumerator =
                new BacktrackingEnumerator<PerfectHashStateSpace2.State, int, IEnumerable<KeyValuePair<string, int>>>
                    ((space, i, decisions, f) => ((PerfectHashStateSpace2)space).Solution(f));
        }

        public IEnumerable<KeyValuePair<string, int>> Find(IEnumerable<string> words, int maxValue)
        {
            var space = new PerfectHashStateSpace2(words, maxValue);
            return _enumerator.First(space);
        }

    }
}
